'''
Created on Jan 14, 2013

@author: Dan
'''
from Quoridor_game import QuoridorState,WHITE,BLACK,DIRECTIONS,QuoridorAction,GetNextLocation
from copy import deepcopy
wallArea = 0

#class improvedQuoridorState(QuoridorState):
#    '''
#    our alternative for the given state. Overriding getSuccessor to eliminate unwanted moves
#    '''
#    def __init__(self, boardProfile = 0, otherState = None , firstInit = False):
#        self.surroundingArea = wallArea
#        QuoridorState.__init__(self, boardProfile, otherState)
#        if boardProfile != 0 or firstInit:
#            self.checkedLocations = [{} for i in range(self.numPieces)] 
#            for pieceNdx in xrange(self.numPieces):
#                self.checkedLocations[pieceNdx][self.locationsW[pieceNdx]] = 'w'
#                self.checkedLocations[pieceNdx][self.locationsB[pieceNdx]] = 'b'
#        else:
#            self.checkedLocations = deepcopy(otherState.checkedLocations)
#            
#    def getSuccessors(self):
#        succDic = {}
#        if (self.curPlayer == WHITE):
#            myLocations = self.locationsW[:]
#            rivalLocations = self.locationsB[:]
#            nextPlayer = BLACK
#        else:
#            myLocations = self.locationsB[:]
#            rivalLocations = self.locationsW[:]
#            nextPlayer = WHITE
#        
#        # Move actions
#        for pieceNdx in xrange(self.numPieces):
#            pieceLoc = myLocations[pieceNdx]
#            if pieceLoc is None: #location is None if the piece has reached the goal (then it is removed from the board) 
#                continue            
#            for dir in DIRECTIONS:    
#                action = QuoridorAction('M',[pieceNdx, dir])       
#                nextLoc = GetNextLocation(pieceLoc, dir)
#                nextRow = nextLoc[0]
#                nextCol = nextLoc[1]   
#                
#                #moves out of board
#                if nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize:
#                    continue
#                #move illegal because of wall
#                if not self._moveOkByWalls(dir, nextRow, nextCol):
#                    continue
#                 # not repeating on visited locations
#                if (nextLoc in self.checkedLocations[pieceNdx].keys()) and\
#                    (self.checkedLocations[pieceNdx][nextLoc] == ((self.curPlayer == WHITE and 'w') or 'b')):
#                    continue
#                
#                # jump-over moves
#                if (nextLoc in rivalLocations or nextLoc in myLocations): 
#                    nextLoc = GetNextLocation(nextLoc, dir)         
#                    nextRow = nextLoc[0]
#                    nextCol = nextLoc[1]                    
#                    
#                    #jump-over move blocked by another piece
#                    if (nextLoc in rivalLocations or nextLoc in myLocations):
#                        continue
#                
#                    #If one of the players has "exited the board" and reached his goal, don't check for walls or boundaries
#                    if (self.curPlayer == WHITE and nextRow >= self.brdSize) or (self.curPlayer == BLACK and nextRow < 0):
#                        pass
#                    else:
#                        if nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize:
#                            continue
#                        if not self._moveOkByWalls(dir, nextRow, nextCol):
#                            continue
#                
#                if (self.curPlayer == WHITE):
#                    newLocationsW = myLocations[:]
#                    if (nextRow >= self.brdSize - 1):
#                        nextLoc = None
#                    newLocationsW[pieceNdx] = nextLoc
#                    newLocationsB = rivalLocations
#                    
#                elif (self.curPlayer == BLACK):
#                    newLocationsB = myLocations[:]
#                    if (nextRow <= 0):
#                        nextLoc = None
#                    newLocationsB[pieceNdx] = nextLoc
#                    newLocationsW = rivalLocations
#                                                   
#                nextState = improvedQuoridorState(0, self)
#                nextState.checkedLocations[pieceNdx][nextLoc] = (self.curPlayer == WHITE and 'w') or 'b'
#                nextState.curPlayer = nextPlayer
#                nextState.turnsLeft = self.turnsLeft - 1
#                nextState.locationsB = newLocationsB
#                nextState.locationsW = newLocationsW    
#                
#                                
#                #Update the next state's "critical walls" (also make sure that the next state is legal)
#                is_legal = True
#                for player in [WHITE, BLACK]:
#                    is_legal = is_legal and nextState._isThereALegalWayToFinish(player)
#                assert is_legal
#                
#                succDic[action] = nextState
#        
#        # Wall actions
#        if (self.curPlayer == WHITE):
#            if self.WallsLeftW <= 0:
#                return succDic
#            newWallsLeftW = self.WallsLeftW - 1
#            newWallsLeftB = self.WallsLeftB
#            
#        elif (self.curPlayer == BLACK):
#            if self.WallsLeftB <= 0:
#                return succDic
#            newWallsLeftW = self.WallsLeftW
#            newWallsLeftB = self.WallsLeftB - 1
#                
#        #copies wall matrix of a certain orientation (Horizontal/Vertical)
#        def _CopyWalls(walls):
#            N = self.brdSize
#            newWalls = [ [ walls[i][j] for j in xrange(N) ] for i in xrange(N-1) ]
#            return newWalls
#        
#######################
#        def isVerticalTrap(wallLoc):
#            '''
#            a function that returns true if the location is the first in a tunnel that can be sealed at the end
#            '''
#            if nextPlayer == WHITE:
#                direction = 'S'
#                targetRow = self.brdSize-1
#                dirXSign = 1
#            else:
#                direction = 'N'
#                targetRow = 0
#                dirXSign = 0
#            
#            loc = (wallLoc[0] + dirXSign,wallLoc[1])
#            if limitedSealableDirection(loc,direction,targetRow):
##                print self
##                print "direction is ",direction
##                print "wall location ",wallLoc
##                print "tunnel entrance location ",loc
##                print "current player is ",self.curPlayer
##                exit()
#                return True
#            return False
#        
#        def limitedSealableDirection(startLoc, direction,targetRow):
#            isTunnel = True
#            isSealed = False
#            endRowLoc = False
#            toBreak = False
#            meInvolved = False
#            loc = startLoc
#            prevLoc = startLoc
#            while True:
#                if loc in myLocations:
#                    meInvolved = True
#                    break
#                if loc[0] == targetRow:
#                    endRowLoc = True
#                    toBreak = True                    
#                if not locBlockedFromTheSide(loc):
#                    isTunnel = False
#                    toBreak = True
#                if not endRowLoc and locBlockedFromAhead(loc, direction):
#                    isSealed = True
#                    toBreak = True
#                
#                if toBreak:
#                    break
#                prevLoc = loc
#                loc = GetNextLocation(prevLoc, direction)
#            if meInvolved:
#                return False
#            
#            if loc == startLoc or isSealed:
#                return False
#            
#            if endRowLoc and isTunnel:
#                return False
#            
#            if not isTunnel:
#                if isSealable(prevLoc, direction):
#                    return True
#            return False
#        
#        def isSealable(currLoc,direction):
#            '''
#            gets a location and direction and returns true if horizontal walls can be added to block it
#            '''
##            print "currLoc ",currLoc,"   ",direction
#            dirXSign = (direction == 'S' and 0) or -1
#            if (self.wallsH[currLoc[0] + dirXSign][currLoc[1] ] == 0 and\
#                self.wallsH[currLoc[0] + dirXSign][min(currLoc[1] + 1,self.brdSize - 1)] == 0) or\
#                (self.wallsH[currLoc[0] + dirXSign][currLoc[1] ] == 0 and\
#                self.wallsH[currLoc[0] + dirXSign][max(currLoc[1] - 1, 0)] == 0):
#                    return True
#            return False
#            
#                    
#        def locBlockedFromTheSide(loc):
#            for dir in ['W','E']:           
#                nextLoc = GetNextLocation(loc, dir)
#                nextRow = nextLoc[0]
#                nextCol = nextLoc[1]        
#                #moves out of board or move illegal because of wall
#                if not(nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize) and\
#                    self._moveOkByWalls(dir, nextRow, nextCol):
#                        return False
#            return True 
#         
#        def locBlockedFromAhead(currLoc,direction):
#            '''
#            verify if the location is blocked in the front
#            '''
#            loc = GetNextLocation(currLoc, direction)
#            nextRow = loc[0]
#            nextCol = loc[1]
#            if self._moveOkByWalls(direction, nextRow, nextCol):
#                return False
#            return True          
#
#        def isInAreaOfRival(index,x,y, isVertical):
#            '''
#            gets an index of a rival and returns true if the wall is in his area
#            '''            
#            d = self.surroundingArea
#            if isVertical:
#                if (y in range(rivalLocations[index][0] - 2 - d,rivalLocations[index][0] + 1 + d + 1 )) and\
#                    (x in range(rivalLocations[index][1] - 1 - d,rivalLocations[index][1] + d + 1)):
#                    return True
#            else:
#                if (y in range(rivalLocations[index][1] - 2 - d,rivalLocations[index][1] + 1 + d + 1 )) and\
#                    (x in range(rivalLocations[index][0] - 1 - d,rivalLocations[index][0] + d + 1)):
#                    return True
#            return False
#            
#        
#        def findRivalback():
#            if self.curPlayer == WHITE:
#                back = 0
#                for index in xrange(self.numPieces):
#                    back = max(back,rivalLocations[index][0])
#            else:
#                back = self.brdSize - 1
#                for index in xrange(self.numPieces):
#                    back = min(back,rivalLocations[index][0])
#            return back
#
#        def wallFarFromFoeVertical(x,y):
#            rivalArea =  findLimits()
##            if self.curPlayer == WHITE:
#            if y < rivalArea[0][0] or y > rivalArea[0][1] or x < rivalArea[1][0] or x > rivalArea[1][1]:
#                return True
#            return False
##            else:
##                if y < rivalArea[0][0] or y > rivalArea[0][1] or x < rivalArea[1][0] or x >= rivalArea[1][1]:
##                    return True
#        
#        def wallFarFromFoesVertical(x,y):
#            '''
#            return True if intended wall location is to far from the rivals
#            '''
#            for index in xrange(self.numPieces):
#                if isInAreaOfRival(index, x, y, True):
#                    return False
#            return True
#        
#        def wallFarFromFoesHorizontal(x,y):
#            for index in xrange(self.numPieces):
#                if isInAreaOfRival(index, x, y, False):
#                    return False
#            return True
#        
#        def wallFarFromFoeHorizontal(x,y):
#            rivalArea =  findLimits()
##            if self.curPlayer == WHITE:
#            if x < rivalArea[0][0] or x > rivalArea[0][1] or y < rivalArea[1][0] or y > rivalArea[1][1]:
#                return True
#            return False
##            else:  
##                if x < rivalArea[0][0] or x >= rivalArea[0][1] or y < rivalArea[1][0] or y > rivalArea[1][1]:
##                    return True
#                
#        def wallBehindFoe(y):
#            if ((self.curPlayer == WHITE and y >= findRivalback()) or (self.curPlayer == BLACK and y < findRivalback())):
#                return True
#            return False
#        
#        def verticalWallHasHorizontalJoin(x,y):
#            if (self.wallsH[y][x] == 0 and self.wallsH[y][x+1] == 0) and (self.wallsV[x][max(y-1,0)] == 0 and self.wallsV[x][min(y+1,self.brdSize - 2)] == 0):
#                return True
#            return False
#
#####################################
#
#        for firstNdx in xrange(self.brdSize - 1):
#            for secondNdx in xrange(self.brdSize - 1):
#      
#                
#                #Handle vertical walls
#                if (self.wallsV[firstNdx][secondNdx] == 0 and self.wallsV[firstNdx][secondNdx+1] == 0 and\
#                    not (self.wallsH[secondNdx][firstNdx] == 1 and self.wallsH[secondNdx][firstNdx+1] == 1) and\
#                    not wallFarFromFoesVertical(firstNdx,secondNdx )and\
#                    not verticalWallHasHorizontalJoin(firstNdx,secondNdx )):
#                    
#                    actionV = QuoridorAction('WV',[firstNdx, secondNdx])
#                    
#                    newWallsV = _CopyWalls(self.wallsV)
#                    newWallsV[firstNdx][secondNdx] = 1
#                    newWallsV[firstNdx][secondNdx+1] = 1   
#                    
#                    newStateV = improvedQuoridorState(0, self)
#                    newStateV.curPlayer = nextPlayer
#                    newStateV.turnsLeft = self.turnsLeft - 1
#                    newStateV.wallsV = newWallsV
#                    newStateV.WallsLeftW = newWallsLeftW
#                    newStateV.WallsLeftB = newWallsLeftB
#
#                    #Check there is a legal way to finish for both players
#                    is_legal = True
#                    for player in [WHITE, BLACK]:
#                        if self._criticalWallsV[player] is None or \
#                            (firstNdx, secondNdx) in self._criticalWallsV[player] or \
#                            (firstNdx, secondNdx+1) in self._criticalWallsV[player]:
#                                is_legal = is_legal and newStateV._isThereALegalWayToFinish(player)
#                                
#                    if is_legal:                        
#                        succDic[actionV] = newStateV
#                
#                #Handle horizontal walls (equivalent to previous case of vertical walls)
#                if ((self.wallsH[firstNdx][secondNdx] == 0 and self.wallsH[firstNdx][secondNdx+1] == 0) and\
#                    not (self.wallsV[secondNdx][firstNdx] == 1 and self.wallsV[secondNdx][firstNdx+1] == 1) and\
#                    not wallFarFromFoesHorizontal(firstNdx,secondNdx ) and\
#                    not (isVerticalTrap((firstNdx,secondNdx)) or isVerticalTrap((firstNdx,secondNdx + 1)))):
#                    
#                    actionH = QuoridorAction('WH',[firstNdx, secondNdx])
#                    newWallsH = _CopyWalls(self.wallsH)
#                    newWallsH[firstNdx][secondNdx] = 1
#                    newWallsH[firstNdx][secondNdx+1] = 1   
#                    
#                    newStateH = improvedQuoridorState(0, self)
#                    newStateH.curPlayer = nextPlayer
#                    newStateH.turnsLeft = self.turnsLeft - 1
#                    newStateH.wallsH = newWallsH  
#                    newStateH.WallsLeftW = newWallsLeftW
#                    newStateH.WallsLeftB = newWallsLeftB
#
#                    #Check there is a legal way to finish for both players
#                    is_legal = True
#                    for player in [WHITE, BLACK]:
#                        if self._criticalWallsH[player] is None or \
#                            (firstNdx, secondNdx) in self._criticalWallsH[player] or \
#                            (firstNdx, secondNdx+1) in self._criticalWallsH[player]:
#                                is_legal = is_legal and newStateH._isThereALegalWayToFinish(player)
#                                
#                    if is_legal:     
#                        succDic[actionH] = newStateH
#            # Pass action
#        if len(succDic) == 0:
#            action = QuoridorAction('P', "")
#            nextState = improvedQuoridorState(0, self)
#            nextState.curPlayer = nextPlayer
#            nextState.turnsLeft = self.turnsLeft - 1
#            succDic[action] = nextState
#        return succDic
    
    
class improvedQuoridorState2(QuoridorState):
    '''
    overriding state with checked locations, a mechanism that remembers moves and don't repeat them
    '''
    def __init__(self, boardProfile = 0, otherState = None , firstInit = False):
        '''
        initiating a matrix that will help us track the locations that have already been visited
        '''
        self.surroundingArea = wallArea
        QuoridorState.__init__(self, boardProfile, otherState)
        if boardProfile != 0 or firstInit:
            self.checkedLocations = [{} for i in range(self.numPieces)] 
            for pieceNdx in xrange(self.numPieces):
                self.checkedLocations[pieceNdx][self.locationsW[pieceNdx]] = 'w'
                self.checkedLocations[pieceNdx][self.locationsB[pieceNdx]] = 'b'
        else:
            self.checkedLocations = deepcopy(otherState.checkedLocations)
            
    def getSuccessors(self):
        succDic = {}
        if (self.curPlayer == WHITE):
            myLocations = self.locationsW[:]
            rivalLocations = self.locationsB[:]
            nextPlayer = BLACK
        else:
            myLocations = self.locationsB[:]
            rivalLocations = self.locationsW[:]
            nextPlayer = WHITE
        
        # Move actions
        for pieceNdx in xrange(self.numPieces):
            pieceLoc = myLocations[pieceNdx]
            if pieceLoc is None: #location is None if the piece has reached the goal (then it is removed from the board) 
                continue            
            for dir in DIRECTIONS:    
                action = QuoridorAction('M',[pieceNdx, dir])       
                nextLoc = GetNextLocation(pieceLoc, dir)
                nextRow = nextLoc[0]
                nextCol = nextLoc[1]   
                
                #moves out of board
                if nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize:
                    continue
                #move illegal because of wall
                if not self._moveOkByWalls(dir, nextRow, nextCol):
                    continue
                # not repeating on visited locations
                if (nextLoc in self.checkedLocations[pieceNdx].keys()) and\
                    (self.checkedLocations[pieceNdx][nextLoc] == ((self.curPlayer == WHITE and 'w') or 'b')):
                    continue
                
                # jump-over moves
                if (nextLoc in rivalLocations or nextLoc in myLocations): 
                    nextLoc = GetNextLocation(nextLoc, dir)         
                    nextRow = nextLoc[0]
                    nextCol = nextLoc[1]                    
                    
                    #jump-over move blocked by another piece
                    if (nextLoc in rivalLocations or nextLoc in myLocations):
                        continue
                
                    #If one of the players has "exited the board" and reached his goal, don't check for walls or boundaries
                    if (self.curPlayer == WHITE and nextRow >= self.brdSize) or (self.curPlayer == BLACK and nextRow < 0):
                        pass
                    else:
                        if nextRow < 0 or nextRow >= self.brdSize or nextCol < 0 or nextCol >= self.brdSize:
                            continue
                        if not self._moveOkByWalls(dir, nextRow, nextCol):
                            continue
                
                if (self.curPlayer == WHITE):
                    newLocationsW = myLocations[:]
                    if (nextRow >= self.brdSize - 1):
                        nextLoc = None
                    newLocationsW[pieceNdx] = nextLoc
                    newLocationsB = rivalLocations
                    
                elif (self.curPlayer == BLACK):
                    newLocationsB = myLocations[:]
                    if (nextRow <= 0):
                        nextLoc = None
                    newLocationsB[pieceNdx] = nextLoc
                    newLocationsW = rivalLocations
                                                   
                nextState = improvedQuoridorState2(0, self)
                nextState.checkedLocations[pieceNdx][nextLoc] = (self.curPlayer == WHITE and 'w') or 'b'
                nextState.curPlayer = nextPlayer
                nextState.turnsLeft = self.turnsLeft - 1
                nextState.locationsB = newLocationsB
                nextState.locationsW = newLocationsW
                                                
                succDic[action] = nextState
        
        # Wall actions
        if (self.curPlayer == WHITE):
            if self.WallsLeftW <= 0:
                return succDic
            newWallsLeftW = self.WallsLeftW - 1
            newWallsLeftB = self.WallsLeftB
            
        elif (self.curPlayer == BLACK):
            if self.WallsLeftB <= 0:
                return succDic
            newWallsLeftW = self.WallsLeftW
            newWallsLeftB = self.WallsLeftB - 1
                
        #copies wall matrix of a certain orientation (Horizontal/Vertical)
        def _CopyWalls(walls):
            N = self.brdSize
            newWalls = [ [ walls[i][j] for j in xrange(N) ] for i in xrange(N-1) ]
            return newWalls
        
######################

#        def findLimits():
#            '''
#            returning the borders which across them we don't put walls
#            '''
#            xLimitLower = 0
#            yLimitLower = 0
#            xLimitUpper = self.brdSize - 1
#            yLimitUpper = self.brdSize - 1
#            for index in xrange(self.numPieces):
#                xLimitLower = max(xLimitLower,rivalLocations[index][0] - self.surroundingArea)
#                yLimitLower = max(yLimitLower,rivalLocations[index][1] - self.surroundingArea)
#                xLimitUpper = min(xLimitUpper,rivalLocations[index][0] + self.surroundingArea)
#                yLimitUpper = min(yLimitUpper,rivalLocations[index][1] + self.surroundingArea)
#            return [[xLimitLower,xLimitUpper],[yLimitLower,yLimitUpper]]
        
        def isInAreaOfRival(index,x,y, isVertical):
            '''
            gets an index of a rival and returns true if the wall is in his area
            '''            
            d = 0
            if isVertical:
                if (rivalLocations[index] != None and y in range(rivalLocations[index][0] - 2 - d,rivalLocations[index][0] + 1 + d + 1 )) and\
                    (x in range(rivalLocations[index][1] - 1 - d,rivalLocations[index][1] + d + 1)):
                    return True
            else:
                if (rivalLocations[index] != None and y in range(rivalLocations[index][1] - 2 - d,rivalLocations[index][1] + 1 + d + 1 )) and\
                    (x in range(rivalLocations[index][0] - 1 - d,rivalLocations[index][0] + d + 1)):
                    return True
            return False
            
        
#        def findRivalback():
#            if self.curPlayer == WHITE:
#                back = 0
#                for index in xrange(self.numPieces):
#                    back = max(back,rivalLocations[index][0])
#            else:
#                back = self.brdSize - 1
#                for index in xrange(self.numPieces):
#                    back = min(back,rivalLocations[index][0])
#            return back

#        def wallFarFromFoeVertical(x,y):
#            rivalArea =  findLimits()
##            if self.curPlayer == WHITE:
#            if y < rivalArea[0][0] or y > rivalArea[0][1] or x < rivalArea[1][0] or x > rivalArea[1][1]:
#                return True
#            return False
#            else:
#                if y < rivalArea[0][0] or y > rivalArea[0][1] or x < rivalArea[1][0] or x >= rivalArea[1][1]:
#                    return True
        
        def wallFarFromFoesVertical(x,y):
            '''
            return True if intended wall location is to far from the rivals
            '''
            for index in xrange(self.numPieces):
                if isInAreaOfRival(index, x, y, True):
                    return False
            return True
        
        def wallFarFromFoesHorizontal(x,y):
            for index in xrange(self.numPieces):
                if isInAreaOfRival(index, x, y, False):
                    return False
            return True
        
#        def wallFarFromFoeHorizontal(x,y):
#            rivalArea =  findLimits()
##            if self.curPlayer == WHITE:
#            if x < rivalArea[0][0] or x > rivalArea[0][1] or y < rivalArea[1][0] or y > rivalArea[1][1]:
#                return True
#            return False
#            else:  
#                if x < rivalArea[0][0] or x >= rivalArea[0][1] or y < rivalArea[1][0] or y > rivalArea[1][1]:
#                    return True
                
#        def wallBehindFoe(y):
#            if ((self.curPlayer == WHITE and y >= findRivalback()) or (self.curPlayer == BLACK and y < findRivalback())):
#                return True
#            return False
        def verticalWallHasNoNeighbors(x,y):
            if (self.wallsH[y][x] == 0 and self.wallsH[y][min(x+1,self.brdSize)] == 0) and (self.wallsV[x][max(y-1,0)] == 0 and self.wallsV[x][min(y+2,self.brdSize - 2)] == 0) and\
            (self.wallsH[min(y+1,self.brdSize-2)][x] == 0 and self.wallsH[min(y+1,self.brdSize-2)][min(x+1,self.brdSize)] == 0) and\
            (self.wallsH[max(y-1,0)][x] == 0 and self.wallsH[max(y-1,0)][min(x+1,self.brdSize)] == 0):
                return True
            return False
####################################

        for firstNdx in xrange(self.brdSize - 1):
            for secondNdx in xrange(self.brdSize - 1):
      
                
                #Handle vertical walls
                if (self.wallsV[firstNdx][secondNdx] == 0 and self.wallsV[firstNdx][secondNdx+1] == 0 and\
                    not (self.wallsH[secondNdx][firstNdx] == 1 and self.wallsH[secondNdx][firstNdx+1] == 1) and\
                    not wallFarFromFoesVertical(firstNdx,secondNdx ) and\
                    not verticalWallHasNoNeighbors(firstNdx,secondNdx)):
                    
                    actionV = QuoridorAction('WV',[firstNdx, secondNdx])
                    
                    newWallsV = _CopyWalls(self.wallsV)
                    newWallsV[firstNdx][secondNdx] = 1
                    newWallsV[firstNdx][secondNdx+1] = 1   
                    
                    newStateV = improvedQuoridorState2(0, self)
                    newStateV.curPlayer = nextPlayer
                    newStateV.turnsLeft = self.turnsLeft - 1
                    newStateV.wallsV = newWallsV
                    newStateV.WallsLeftW = newWallsLeftW
                    newStateV.WallsLeftB = newWallsLeftB

                    #Check there is a legal way to finish for both players
                    is_legal = True
                    for player in [WHITE, BLACK]:
                        if self._criticalWallsV[player] is None or \
                            (firstNdx, secondNdx) in self._criticalWallsV[player] or \
                            (firstNdx, secondNdx+1) in self._criticalWallsV[player]:
                                is_legal = is_legal and newStateV._isThereALegalWayToFinish(player)
                                
                    if is_legal:                        
                        succDic[actionV] = newStateV
                
                #Handle horizontal walls (equivalent to previous case of vertical walls)
                if ((self.wallsH[firstNdx][secondNdx] == 0 and self.wallsH[firstNdx][secondNdx+1] == 0) and\
                    not (self.wallsV[secondNdx][firstNdx] == 1 and self.wallsV[secondNdx][firstNdx+1] == 1) and\
                    not wallFarFromFoesHorizontal(firstNdx,secondNdx )):
                    actionH = QuoridorAction('WH',[firstNdx, secondNdx])
                    newWallsH = _CopyWalls(self.wallsH)
                    newWallsH[firstNdx][secondNdx] = 1
                    newWallsH[firstNdx][secondNdx+1] = 1   
                    
                    newStateH = improvedQuoridorState2(0, self)
                    newStateH.curPlayer = nextPlayer
                    newStateH.turnsLeft = self.turnsLeft - 1
                    newStateH.wallsH = newWallsH  
                    newStateH.WallsLeftW = newWallsLeftW
                    newStateH.WallsLeftB = newWallsLeftB

                    #Check there is a legal way to finish for both players
                    is_legal = True
                    for player in [WHITE, BLACK]:
                        if self._criticalWallsH[player] is None or \
                            (firstNdx, secondNdx) in self._criticalWallsH[player] or \
                            (firstNdx, secondNdx+1) in self._criticalWallsH[player]:
                                is_legal = is_legal and newStateH._isThereALegalWayToFinish(player)
                                
                    if is_legal:     
                        succDic[actionH] = newStateH
                        
            # Pass action
        if len(succDic) == 0:
            action = QuoridorAction('P', "")
            passState = improvedQuoridorState2(0, self)
            passState.curPlayer = nextPlayer
            passState.turnsLeft = self.turnsLeft - 1
            succDic[action] = passState
        return succDic
